package LeetCode._01算法入门.day11递归回溯;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 挚爱之夕
 * @date 2022-03-02 - 03 - 02 - 15:47
 * @Description 给定一个字符串s，通过将字符串s中的每个字母转变大小写，我们可以获得一个新的字符串。
 * 返回所有可能得到的字符串集合，以任意顺序返回输出。
 * @Version 中等
 */
public class _784字母大小写全排列 {
    static String s = "a1b2";

    @Test
    public void solve(){
        List<String> res = letterCasePermutation(s);
        System.out.println(res);
    }
    StringBuilder sb = new StringBuilder();
    List<String> res = new ArrayList<>();
    public List<String> letterCasePermutation(String s) {
        dfs(s, 0);
        return res;
    }

    public void dfs(String s, int index){
        if(index == s.length()){    //处理完毕
            res.add(sb.toString());
            return;
        }
        char c = s.charAt(index);
        //是字母才考虑是否转大小写
        if(Character.isLetter(c)){
            //改变当前索引字母，处理下一个字符
            sb.append(change(s.charAt(index)));
            dfs(s, index + 1);

            //回溯
            sb.deleteCharAt(sb.length() - 1);
        }

        //不改变当前字母，处理下一个字母
        sb.append(s.charAt(index));
        dfs(s, index + 1);

        //这是一个坑，每次返回上一个栈空间，应该删除最后的字符，否则sb很长
        sb.deleteCharAt(sb.length() - 1);
    }
    //大小互转
    public char change(char c){
        if(c >= 'a' && c <= 'z'){
            return (char) (c - 32);
        }else if(c >= 'A' && c <= 'Z'){
            return (char) (c + 32);
        }else{
            return c;
        }
    }
}
